fn sort(a: &mut Vec<i32>, start: usize, end: usize) {
    for i in a.iter() {
        println!("{}", i);
    }
    let ret = divide(a, start, end);
    if start < ret {
        sort(a, start, ret-1);
    }
    if ret+1 < end {
        sort(a, ret+1, end);
    }
}

fn divide(a: &mut Vec<i32>, start: usize, end: usize) -> usize {
    let pivot = end;
    if end <= start {
        return pivot
    }
    let mut i = start;
    let mut j = end;
    let p = a[pivot];

    while i < j  {
        if a[i] <= p {
            i += 1;
            continue;
        }
        if a[j] > p {
            j -= 1;
            continue;
        }

        if i < j {
            println!("swap {} with {}, v: {} {}", i, j, a[i], a[j]);
            let tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }
    if j >= pivot {
        let tmp = a[j];
        a[j] = a[pivot];
        a[pivot] = tmp;
    }
    return j;
}

#[test]
fn test_quick() {
    let mut a = vec![1, 9, 8, 5, 8, 7, 2];
    let len = a.len();
    sort(&mut a, 0, len - 1);
    assert_eq!(a[0], 1);
    assert_eq!(a[len - 1], 9);
}
